package oct2013;

import java.util.ArrayList;
import java.util.Arrays;

public class SubsetsII {
	ArrayList<ArrayList<Integer>> res;
	int[] val, num;
	int cnt, n;

	public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
		res = new ArrayList<ArrayList<Integer>>();
		n = num.length;
		this.num = num;
		cnt = 0;
		val = new int[n];
		Arrays.sort(num);
		dfs(0);
		return res;
	}

	void dfs(int i) {
		if (i == n) {
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int j = 0; j < cnt; ++j) {
				list.add(val[j]);
			}
			res.add(list);
			return;
		}
		int j = i + 1;
		while (j < n && num[j] == num[i])
			j++;
		dfs(j);
		int tmp = cnt;
		for (; i < j; ++i) {
			val[cnt++] = num[i];
			dfs(j);
		}
		cnt = tmp;
	}

}
